package com.cobla.struct.str;

/**
 * 字符串 模式匹配 kmp算法
 */
public class Kmp {

    /**
     * 求字串的 next 数组
     * @param c
     * @return
     */
    public static int[] getNext(char[] c){
        int[] next = new int[c.length];
        next[0] = -1;
        for (int i = 0, j = -1; i < c.length - 1;) {
            if (j == -1 || c[i] == c[j]) {
                ++i;
                ++j;
                // 前面的都匹配时
                // 如果当前匹配，则当子串 i位置 与父串不匹配时
                // 仍然会选择 c[j] == c[i]，相同的元素进行匹配
                // 因此很显然，当 i元素与j元素相同时，直接跳过这个匹配过程即可
                if (c[i] != c[j]) {
                    next[i] = j;
                } else {
                    next[i] = next[j];
                }
            } else {
                j = next[j];
            }
        }
        return next;
    }

    /**
     * 成功匹配返回 child 在 father 中的起始下标
     * @param father
     * @param child
     * @return
     */
    public static int kmpSearch(char[] father, char[] child) {
        int[] next = getNext(child);
        int j = 0;
        int i = 0;
        for (; i < father.length && j < child.length;) {
            if (j == -1 || father[i] == child[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == child.length) {
            return i - j;
        }
        return -1;
    }

}
